package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.Backtracking;

import java.util.*;

/**
 * https://leetcode.com/problems/letter-combinations-of-a-phone-number/
 * 9宫格键盘
 * 很基本的回溯
 * 0 <= digits.length <= 4
 * digits[i] is a digit in the range ['2', '9']
 *
 * @author tzp
 * @since 2020/10/16
 */
public class LC17 implements Backtracking {
    Map<Integer, String> mappings = new HashMap<>();

    public void initMapping() {
        mappings.put(2, "abc");
        mappings.put(3, "def");
        mappings.put(4, "ghi");
        mappings.put(5, "jkl");
        mappings.put(6, "mno");
        mappings.put(7, "pqrs");
        mappings.put(8, "tuv");
        mappings.put(9, "wxyz");
    }

    List<String> result = new ArrayList<>();

    public List<String> letterCombinations(String digits) {
        if (digits == null || digits.length() == 0) return Collections.emptyList();
        initMapping();
        backtracking(digits, digits.length(), new ArrayList<>());
        return result;
    }

    public void backtracking(String digits, int remainLength, List<String> path) {
        if (remainLength == 0) {
            result.add(String.join("", path));
        } else {
            Integer cur = Integer.parseInt(
                    digits.substring(digits.length() - remainLength, digits.length() - remainLength + 1));
            String choices = mappings.get(cur);
            for (int i = 0; i < choices.length(); i++) {
                path.add(choices.substring(i, i + 1));
                backtracking(digits, remainLength - 1, path);
                path.remove(path.size() - 1);
            }
        }
    }

    public static void main(String[] args) {
        System.out.println(new LC17().letterCombinations("23"));
    }
}
